{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Univalued Binary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isUnivalTree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #单值二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>如果二叉树每个节点都具有相同的值，那么该二叉树就是<em>单值</em>二叉树。</p>\n",
    "\n",
    "<p>只有给定的树是单值二叉树时，才返回&nbsp;<code>true</code>；否则返回 <code>false</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/29/screen-shot-2018-12-25-at-50104-pm.png\" style=\"height: 159px; width: 200px;\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>[1,1,1,1,1,null,1]\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/29/screen-shot-2018-12-25-at-50050-pm.png\" style=\"height: 158px; width: 200px;\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>[2,2,2,5,2]\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li>给定树的节点数范围是&nbsp;<code>[1, 100]</code>。</li>\n",
    "\t<li>每个节点的值都是整数，范围为&nbsp;<code>[0, 99]</code>&nbsp;。</li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [univalued-binary-tree](https://leetcode.cn/problems/univalued-binary-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [univalued-binary-tree](https://leetcode.cn/problems/univalued-binary-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,1,1,1,1,null,1]', '[2,2,2,5,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root:\n",
    "            if root.left and (root.left.val != root.val or not self.isUnivalTree(root.left)):\n",
    "                return False\n",
    "            if root.right and (root.right.val != root.val or not self.isUnivalTree(root.right)):\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        x = root.val\n",
    "\n",
    "        def dfs(o) -> bool:\n",
    "            if o is None:\n",
    "                return True\n",
    "            return o.val == x and dfs(o.left) and dfs(o.right)\n",
    "\n",
    "        return dfs(root)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root==None: return True\n",
    "        if not self.isUnivalTree(root.left) or not self.isUnivalTree(root.right) or root.left and root.left.val!=root.val or root.right and root.right.val!=root.val:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "\n",
    "        if root.left:\n",
    "            if root.val != root.left.val or not self.isUnivalTree(root.left):\n",
    "                return False\n",
    "\n",
    "        if root.right:\n",
    "            if root.val != root.right.val or not self.isUnivalTree(root.right):\n",
    "                return False\n",
    "        \n",
    "        return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        if root.left:\n",
    "            if root.val != root.left.val or not self.isUnivalTree(root.left):\n",
    "                return False\n",
    "        if root.right:\n",
    "            if root.val != root.right.val or not self.isUnivalTree(root.right):\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: TreeNode) -> bool:\n",
    "        ans = set()\n",
    "        def dfs(node):\n",
    "            if node is None:\n",
    "                return \n",
    "            ans.add(node.val)\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "        dfs(root)\n",
    "        print(ans)\n",
    "        return True if len(ans) == 1 else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        \n",
    "        if root.left:\n",
    "            if root.val != root.left.val or not self.isUnivalTree(root.left):\n",
    "                return False\n",
    "            \n",
    "        if root.right:\n",
    "            if root.val != root.right.val or not self.isUnivalTree(root.right):\n",
    "                return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self,root:TreeNode) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        if root.left and root.left.val !=root.val:\n",
    "            return False\n",
    "        if root.right and root.right.val != root.val:\n",
    "            return False\n",
    "        return self.isUnivalTree(root.left) and self.isUnivalTree(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.v = None\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root is None:\n",
    "            return True\n",
    "        if self.v is None:\n",
    "            self.v = root.val\n",
    "        if self.v != root.val:\n",
    "            return False\n",
    "        return self.isUnivalTree(root.left) and self.isUnivalTree(root.right)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: TreeNode) -> bool:\n",
    "        v = root.val\n",
    "        def dfs(node):\n",
    "            if node:\n",
    "                yield node.val \n",
    "                yield from dfs(node.left)\n",
    "                yield from dfs(node.right)\n",
    "        return all(v == other for other in dfs(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "      def dfs(root,par):\n",
    "        if not root:\n",
    "          return True\n",
    "        else:\n",
    "          \n",
    "          return root.val==par and dfs(root.left,root.val) and dfs(root.right,root.val)\n",
    "      return  dfs(root,root.val)\n",
    "          \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root is None:\n",
    "            return True\n",
    "\n",
    "        if root.left is not None:\n",
    "            if not self.isUnivalTree(root.left):\n",
    "                return False\n",
    "            if root.val != root.left.val:\n",
    "                return False\n",
    "\n",
    "        if root.right is not None:\n",
    "            if not self.isUnivalTree(root.right):\n",
    "                return False\n",
    "            if root.val != root.right.val:\n",
    "                return False\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        \n",
    "        if root.left == None and root.right == None:\n",
    "            return True\n",
    "        elif root.left != None and root.right == None:\n",
    "            if root.val != root.left.val:\n",
    "                return False\n",
    "            else:\n",
    "                return self.isUnivalTree(root.left)\n",
    "        elif root.left == None and root.right != None:\n",
    "            if root.val != root.right.val:\n",
    "                return False\n",
    "            else:\n",
    "                return self.isUnivalTree(root.right)\n",
    "        else:\n",
    "            if root.val != root.left.val or root.val != root.right.val:\n",
    "                return False\n",
    "            else:\n",
    "                rs = self.isUnivalTree(root.right)\n",
    "\n",
    "                if rs:\n",
    "                    return self.isUnivalTree(root.left)\n",
    "                else:\n",
    "                    return False\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        value = root.val\n",
    "        def dfs(root,value):\n",
    "            if not root:\n",
    "                return True\n",
    "            return root.val == value and dfs(root.left,value) and dfs(root.right,value)\n",
    "        return dfs(root,value)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "\n",
    "        if root.left:\n",
    "            if root.val != root.left.val or not self.isUnivalTree(root.left):\n",
    "                return False\n",
    "        \n",
    "        if root.right:\n",
    "            if root.val != root.right.val or not self.isUnivalTree(root.right):\n",
    "                return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from dataclasses import dataclass\n",
    "\n",
    "@dataclass\n",
    "class Solution:\n",
    "    val: int = -1\n",
    "    def isUnivalTree(self, root: TreeNode) -> bool:\n",
    "        # 给定树的节点数范围是 [1, 100]。\n",
    "        if not root:\n",
    "            return True\n",
    "        if self.val == -1:\n",
    "            self.val = root.val\n",
    "        if root.val != self.val:\n",
    "            return False\n",
    "        return self.isUnivalTree(root.left) and self.isUnivalTree(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        return (root.left is None or self.isUnivalTree(root.left) and root.left.val == root.val) and \\\n",
    "               (root.right is None or self.isUnivalTree(root.right) and root.right.val == root.val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        target = root.val\n",
    "        def traverse(node,target):\n",
    "            if node is None:\n",
    "                return True\n",
    "            if node.val != target:\n",
    "                return False\n",
    "            return traverse(node.left,target) and traverse(node.right,target)\n",
    "            \n",
    "        return traverse(root,target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        global s\n",
    "        s = set()\n",
    "\n",
    "        return self.helper(root)\n",
    "\n",
    "    def helper(self, root):\n",
    "        global s\n",
    "\n",
    "        if root:\n",
    "            s.add(root.val)\n",
    "            if len(s) > 1:\n",
    "                return False\n",
    "            self.helper(root.left)\n",
    "            self.helper(root.right)\n",
    "        \n",
    "        return len(s) == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 注意：python 代码由 chatGPT\\U0001f916 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。\n",
    "# 本代码已经通过力扣的测试用例，应该可直接成功提交。\n",
    "\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: TreeNode) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        self.prev = root.val\n",
    "        self.isUnival = True\n",
    "        self.traverse(root)\n",
    "        return self.isUnival\n",
    "    \n",
    "    def traverse(self, root: TreeNode) -> None:\n",
    "        if not root or not self.isUnival:\n",
    "            return\n",
    "        if root.val != self.prev:\n",
    "            self.isUnival = False\n",
    "            return\n",
    "        self.traverse(root.left)\n",
    "        self.traverse(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        self.start = root.val\n",
    "        def isut(root):\n",
    "            if not root:\n",
    "                return True\n",
    "            \n",
    "            if root.val != self.start:\n",
    "                return False\n",
    "            \n",
    "            return isut(root.left) and isut(root.right)\n",
    "\n",
    "        return isut(root)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return True\n",
    "            if root.val != val:\n",
    "                return False\n",
    "            return dfs(root.left) and dfs(root.right)\n",
    "\n",
    "        if not root:\n",
    "            return True\n",
    "        val = root.val\n",
    "        return dfs(root)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: TreeNode) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        \n",
    "        if root.left:\n",
    "            if root.val != root.left.val or not self.isUnivalTree(root.left):\n",
    "                return False\n",
    "        \n",
    "        if root.right:\n",
    "            if root.val != root.right.val or not self.isUnivalTree(root.right):\n",
    "                return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        if root.left:\n",
    "            if root.val != root.left.val or not self.isUnivalTree(root.left):\n",
    "                return False\n",
    "        if root.right:\n",
    "            if root.val != root.right.val or not self.isUnivalTree(root.right):\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return\n",
    "\n",
    "        self.pre=root.val\n",
    "        self.flag=True\n",
    "        self.traverse(root)\n",
    "        return self.flag\n",
    "\n",
    "    def traverse(self, root):\n",
    "        if not root or not self.flag:\n",
    "            return\n",
    "        if self.pre!=root.val:\n",
    "            self.flag=False\n",
    "            return \n",
    "        \n",
    "        self.traverse(root.left)\n",
    "        self.traverse(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        nums = []\n",
    "        def pre_order(node):\n",
    "            if not node:\n",
    "                return \n",
    "            nums.append(node.val)\n",
    "            pre_order(node.left)\n",
    "            pre_order(node.right)\n",
    "        pre_order(root)\n",
    "        nums.sort()\n",
    "        return nums[0] == nums[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "\n",
    "        if not root: return True\n",
    "\n",
    "        targetVal = root.val\n",
    "\n",
    "        def dfs(node):\n",
    "            nonlocal targetVal\n",
    "            if not node: return True\n",
    "\n",
    "            if node.val != targetVal:\n",
    "                return False\n",
    "            return dfs(node.left) and dfs(node.right)\n",
    "\n",
    "        return dfs(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        self.flag = True\n",
    "        self.traverse(root)\n",
    "        return self.flag\n",
    "    \n",
    "    def traverse(self, root):\n",
    "        if not root:\n",
    "            return\n",
    "        \n",
    "        if root.left and root.left.val != root.val:\n",
    "            self.flag = False\n",
    "        \n",
    "        if root.right and root.right.val != root.val:\n",
    "            self.flag = False\n",
    "        \n",
    "        self.traverse(root.left)\n",
    "        self.traverse(root.right)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "\n",
    "        def isUnival(root, value):\n",
    "            if not root:\n",
    "                return True\n",
    "            \n",
    "            return root.val == value and isUnival(root.left, value) and isUnival(root.right, value)\n",
    "\n",
    "\n",
    "        return isUnival(root, root.val) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        a = root.val\n",
    "        while root:\n",
    "            if cur := root.left:\n",
    "                while cur.right and cur.right != root:\n",
    "                    cur = cur.right\n",
    "                if cur.right:\n",
    "                    cur.right = None\n",
    "                else:\n",
    "                    cur.right = root\n",
    "                    root = root.left\n",
    "                    continue\n",
    "            if root.val != a:\n",
    "                return False\n",
    "            root = root.right\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        lst=[]\n",
    "        def find_note(note):\n",
    "            if note is None:\n",
    "                return\n",
    "            lst.append(note.val)\n",
    "            find_note(note.left)\n",
    "            find_note(note.right)\n",
    "        find_note(root)\n",
    "        if len(set(lst))==1:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def getlist(root):\n",
    "            if not root:\n",
    "                return []\n",
    "            return [root.val]+getlist(root.left)+getlist(root.right)\n",
    "        ls=getlist(root)\n",
    "        if len(ls)==1:\n",
    "            return True\n",
    "        for i in range(len(ls)-1):\n",
    "            if ls[i]!=ls[i+1]:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root:\n",
    "            if root.left and (root.left.val != root.val or not self.isUnivalTree(root.left)):\n",
    "                return False\n",
    "            if root.right and (root.right.val != root.val or not self.isUnivalTree(root.right)):\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        self.res = True\n",
    "        self.val = root.val\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            if root.val != self.val:\n",
    "                self.res = False\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "        \n",
    "        dfs(root)\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        v = root.val\n",
    "\n",
    "        def f(node):\n",
    "            if not node:\n",
    "                return True\n",
    "            if node.val != v:\n",
    "                return False\n",
    "            return f(node.left) and f(node.right)\n",
    "        \n",
    "        return f(root.left) and f(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        return (not root.left or self.isUnivalTree(root.left) and root.left.val == root.val) and \\\n",
    "               (not root.right or self.isUnivalTree(root.right) and root.right.val == root.val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        global s\n",
    "        s = set()\n",
    "\n",
    "        return self.helper(root)\n",
    "\n",
    "    def helper(self, root):\n",
    "        global s\n",
    "\n",
    "        if root:\n",
    "            s.add(root.val)\n",
    "            if len(s) > 1:\n",
    "                return False\n",
    "            self.helper(root.left)\n",
    "            self.helper(root.right)\n",
    "        \n",
    "        return len(s) == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return True\n",
    "            if node.val != v:\n",
    "                return False\n",
    "            return dfs(node.left) and dfs(node.right)\n",
    "            \n",
    "        v = root.val \n",
    "        return dfs(root)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        ans=True\n",
    "        def dfs(r):\n",
    "            nonlocal ans\n",
    "            if not r:\n",
    "                return \n",
    "            if r.val!=root.val:\n",
    "                ans=False\n",
    "            dfs(r.left)\n",
    "            dfs(r.right)\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        if root.left:\n",
    "            if root.val != root.left.val or not self.isUnivalTree(root.left):\n",
    "                return False\n",
    "        if root.right:\n",
    "            if root.val != root.right.val or not self.isUnivalTree(root.right):\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        # 创建一个双端队列\n",
    "        q = collections.deque()\n",
    "        q.append(root)\n",
    "        val = root.val\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            if not node:\n",
    "                continue\n",
    "            if val != node.val:\n",
    "                return False\n",
    "            q.append(node.left)\n",
    "            q.append(node.right)\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        num = root.val\n",
    "        queue = deque([root])\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if node.val != num:\n",
    "                return False\n",
    "            if node.left:\n",
    "                queue.append(node.left)\n",
    "            if node.right:\n",
    "                queue.append(node.right)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        if root.left:\n",
    "            if root.val != root.left.val or not self.isUnivalTree(root.left):\n",
    "                return False\n",
    "        if root.right:\n",
    "            if root.val != root.right.val or not self.isUnivalTree(root.right):\n",
    "                return False\n",
    "        return True\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def check(node, value):\n",
    "            if not node:\n",
    "                return True\n",
    "            if node.val != value:\n",
    "                return False\n",
    "            return check(node.left, value) and check(node.right, value)\n",
    "        \n",
    "        return check(root, root.val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: TreeNode) -> bool:\n",
    "        # if not root:\n",
    "        #     return True\n",
    "        \n",
    "        # if root.left:\n",
    "        #     if root.val != root.left.val or not self.isUnivalTree(root.left):\n",
    "        #         return False\n",
    "        \n",
    "        # if root.right:\n",
    "        #     if root.val != root.right.val or not self.isUnivalTree(root.right):\n",
    "        #         return False\n",
    "        \n",
    "        # return True\n",
    "        if root==None:\n",
    "            return True\n",
    "        if root.left and root.val !=root.left.val:\n",
    "            return False\n",
    "        if root.right and root.val!=root.right.val:\n",
    "            return False\n",
    "        return self.isUnivalTree(root.left) and self.isUnivalTree(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        return len(set(self.get(root)))==1\n",
    "    \n",
    "    def get(self,root):\n",
    "        if not root:\n",
    "            return []\n",
    "        res = []\n",
    "        res.append(root.val)\n",
    "        res.extend(self.get(root.left))\n",
    "        res.extend(self.get(root.right))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def recur(root,v):\n",
    "            if root.val!=v:\n",
    "                return False\n",
    "            if root.left and not recur(root.left,v):\n",
    "                return False\n",
    "            if root.right and not recur(root.right,v):\n",
    "                return False\n",
    "            return True\n",
    "        \n",
    "        return recur(root,root.val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: TreeNode) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        \n",
    "        if root.left:\n",
    "            if root.val != root.left.val or not self.isUnivalTree(root.left):\n",
    "                return False\n",
    "        \n",
    "        if root.right:\n",
    "            if root.val != root.right.val or not self.isUnivalTree(root.right):\n",
    "                return False\n",
    "        \n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        res = True\n",
    "        def s(node):\n",
    "            nonlocal res\n",
    "            if node:\n",
    "                if node.val != root.val:\n",
    "                    res = False\n",
    "                    return\n",
    "                s(node.left)\n",
    "                s(node.right)\n",
    "        s(root)\n",
    "        return res\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "from queue import Queue\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\r\n",
    "        self.val = root.val\r\n",
    "        self.res = True\r\n",
    "        \r\n",
    "        Q = Queue()\r\n",
    "        Q.put(root)\r\n",
    "\r\n",
    "        while not Q.empty():\r\n",
    "\r\n",
    "            cur_visit = Q.get()\r\n",
    "\r\n",
    "            if not cur_visit:\r\n",
    "                continue \r\n",
    "\r\n",
    "            if cur_visit.val != self.val:\r\n",
    "                self.res = False\r\n",
    "                break\r\n",
    "            \r\n",
    "            Q.put(cur_visit.left)\r\n",
    "            Q.put(cur_visit.right)\r\n",
    "\r\n",
    "        return self.res\r\n",
    "    \r\n",
    "    def isUnivalTree1(self, root: Optional[TreeNode]) -> bool:\r\n",
    "        self.val = root.val\r\n",
    "        self.res = True\r\n",
    "        self.traverse(root)\r\n",
    "\r\n",
    "        return self.res\r\n",
    "    \r\n",
    "    def traverse(self, root: Optional[TreeNode]) -> None:\r\n",
    "\r\n",
    "        if not root:\r\n",
    "            return\r\n",
    "        \r\n",
    "        if root.val != self.val:\r\n",
    "            self.res = False\r\n",
    "        \r\n",
    "        self.traverse(root.left)\r\n",
    "\r\n",
    "        self.traverse(root.right)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        self.univalued = True\n",
    "        self.dfs(root, root.val)\n",
    "        return self.univalued\n",
    "    def dfs(self, root, unival):\n",
    "        if root == None:\n",
    "            return\n",
    "        if root.val != unival:\n",
    "            self.univalued = False\n",
    "            return\n",
    "        self.dfs(root.left, unival)\n",
    "        self.dfs(root.right, unival)\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\r\n",
    "            \r\n",
    "        def dfs(node):\r\n",
    "            if not node:\r\n",
    "                return True\r\n",
    "            if node.val != root.val:\r\n",
    "                return False\r\n",
    "            return dfs(node.left) and dfs(node.right)\r\n",
    "            \r\n",
    "        return dfs(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def dfs(root, value):\n",
    "            if root == None:\n",
    "                return True\n",
    "            if root.val != value:\n",
    "                return False\n",
    "            return dfs(root.left, value) and dfs(root.right, value)\n",
    "        if root == None:\n",
    "            return True\n",
    "        return dfs(root, root.val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return True\n",
    "            if (root.left and root.val!=root.left.val) or (root.right and root.val!=root.right.val):\n",
    "                return False\n",
    "            return dfs(root.left) and dfs(root.right)    \n",
    "        return dfs(root)\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: TreeNode) -> bool:\n",
    "        if root:\n",
    "            if root.left and (root.left.val != root.val or not self.isUnivalTree(root.left)):\n",
    "                return False\n",
    "            if root.right and (root.right.val != root.val or not self.isUnivalTree(root.right)):\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root is None:\n",
    "            return True\n",
    "        result = True\n",
    "        def dfs(node, target):\n",
    "            if node is None:\n",
    "                return True\n",
    "            if node.val != target:\n",
    "                return False\n",
    "            return dfs(node.left, target) and dfs(node.right, target)\n",
    "        return dfs(root, root.val)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        # res = []\n",
    "        v = root.val\n",
    "        def traversal(root: Optional):\n",
    "            # if not root:\n",
    "            #     return None\n",
    "            # else:\n",
    "            #     print(root.val)\n",
    "            #     # if v != root.val:\n",
    "            #     #     return False\n",
    "            #     # else:\n",
    "            #     return v == root.val and traversal(root.left) and traversal(root.right)\n",
    "            return root is None or (v == root.val and traversal(root.left) and traversal(root.right))\n",
    "                # if len(res) > 0:\n",
    "                #     if root.val != res[0]:\n",
    "                #         return False\n",
    "                # else:\n",
    "                #     return res.append(root.val) and traversal(root.left, res) and traversal(root.right, res)\n",
    "                # return traversal(root.left, res) and traversal(root.right, res)\n",
    "                # traversal(root.left, res) \n",
    "                # traversal(root.right, res)\n",
    "        # print(traversal(root))\n",
    "        return traversal(root)        \n",
    "        # traversal(root, res)\n",
    "        # if traversal(root) == None:\n",
    "        #     return True\n",
    "        # else: return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: TreeNode) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        value = root.val\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return True\n",
    "            if value != node.val:\n",
    "                return False\n",
    "            return dfs(node.left) and dfs(node.right)\n",
    "        return dfs(root)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "\n",
    "        def dfs(node):\n",
    "            if node is None:\n",
    "                return True \n",
    "            \n",
    "            if node.left:\n",
    "                if node.left.val != node.val or not dfs(node.left):\n",
    "                    return False\n",
    "            \n",
    "            if node.right:\n",
    "                if node.right.val != node.val or not dfs(node.right):\n",
    "                    return False\n",
    "\n",
    "            return True\n",
    "\n",
    "\n",
    "        return dfs(root) \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        num = root.val\n",
    "        def dfs(root):\n",
    "            nonlocal num\n",
    "            if root.val != num:\n",
    "                return False\n",
    "            if root.left:\n",
    "                if not dfs(root.left):\n",
    "                    return False\n",
    "            if root.right:\n",
    "                if not dfs(root.right):\n",
    "                    return False\n",
    "            return True\n",
    "        return dfs(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        \n",
    "        if root.left:\n",
    "            if root.val != root.left.val or not self.isUnivalTree(root.left):\n",
    "                return False\n",
    "        \n",
    "        if root.right:\n",
    "            if root.val != root.right.val or not self.isUnivalTree(root.right):\n",
    "                return False\n",
    "        \n",
    "        return True\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        temp = root.val\n",
    "\n",
    "        def getRes(root):\n",
    "            nonlocal temp\n",
    "            if root.val != temp:\n",
    "                return False\n",
    "            left = right = True\n",
    "            if root.left!=None:\n",
    "                left = getRes(root.left)\n",
    "            if root.right!=None:\n",
    "                right = getRes(root.right)\n",
    "            return left and right\n",
    "\n",
    "        return getRes(root) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        ans = True\n",
    "        def dfs(node, pre):\n",
    "            if pre.val != node.val:\n",
    "                nonlocal ans\n",
    "                ans = False\n",
    "                return\n",
    "            else:\n",
    "                if node.left:\n",
    "                    dfs(node.left, node)\n",
    "                if node.right:\n",
    "                    dfs(node.right, node)\n",
    "        dummy = TreeNode(root.val)\n",
    "        dummy.left = root\n",
    "        dfs(root, dummy)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        lst=[]\n",
    "        def find_note(note):\n",
    "            if note is None:\n",
    "                return\n",
    "            lst.append(note.val)\n",
    "            find_note(note.left)\n",
    "            find_note(note.right)\n",
    "        find_note(root)\n",
    "        if len(set(lst))==1:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        # if not root:\n",
    "        #     return True\n",
    "        # if root.left:\n",
    "        #     if root.val!=root.left.val or  not self.isUnivalTree(root.left):\n",
    "        #         return False\n",
    "        # if root.right:\n",
    "        #     if root.val!=root.right.val or not self.isUnivalTree(root.right):\n",
    "        #         return False\n",
    "        # return True\n",
    "        if root==None:\n",
    "            return True\n",
    "        if root.left and root.val !=root.left.val:\n",
    "            return False\n",
    "        if root.right and root.val!=root.right.val:\n",
    "            return False\n",
    "        return self.isUnivalTree(root.left) and self.isUnivalTree(root.right)\n",
    "        \n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
